public class Demo52 {
    class Treenode{
        int val;
        Treenode right;
        Treenode left;
    }
    public Treenode root = null;
    public void remove(int key) {
        Treenode partent = null;
        Treenode cur = root;
        while (cur != null) {
            if (cur.val < key) {
                partent = cur;
                break;
            } else if (cur.val > key) {
                partent = cur;
                cur = cur.right;
            } else {
                removenode(cur, partent);
            }
        }
    }

        public void removenode(Treenode cur,Treenode partent) {
            if (cur.left == null) {
                if (root == cur) {
                    root = cur.right;
                } else if (cur == partent.left) {
                    partent.left = cur.right;
                } else {
                    partent.right = cur.right;
                }

            } else if (cur.right == null) {
                if(root == cur){
                    root = cur.left;
                }else if(cur == partent.left){
                    partent.left = cur.left;
                }
                else{
                    partent.right = cur.left;
                }
            } else {
Treenode targetParent = cur;
Treenode target = cur.right;
while(target.left != null){
    targetParent = target;
    target = target.left;
}
cur.val = target.val;
if(targetParent.left == target){
    targetParent.left = target.right;
}
else{
    targetParent.right =target.right;
}
            }
        }
}




